// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"cmd/internal/src"
	"fmt"
	"math"
)

type branch int

const (
	unknown branch = iota
	positive
	negative
)

// 关系表示两个对象之间可能存在的关系集
// 变量对（v，w）。在没有先验知识的情况下
// 掩码为lt | eq | gt，表示v可以小于、等于或
// 大于w。当执行路径在条件上分支时
// `v op w`更新关系集以排除任何
// 由于'v op w'为真（或假），关系不可能存在。
// None
// 例如。
// None
// r:=关系（…）
// None
// 如果v<w{
// newR:=r&lt
// }
// 如果v>=w{
// newR:=r&（等式| gt）
// }
// 如果v！=w{
// newR:=r&（lt | gt）
// }
type relation uint

const (
	lt relation = 1 << iota
	eq
	gt
)

var relationStrings = [...]string{
	0: "none", lt: "<", eq: "==", lt | eq: "<=",
	gt: ">", gt | lt: "!=", gt | eq: ">=", gt | eq | lt: "any",
}

func (r relation) String() string {
	if r < relation(len(relationStrings)) {
		return relationStrings[r]
	}
	return fmt.Sprintf("relation(%d)", uint(r))
}

// 域表示变量对的域，其中
// 关系的重要性是众所周知的。例如，为未签名对象学习的关系
// 无法将对传输到有符号对，因为相同的位
// 代表性可以意味着其他东西。
type domain uint

const (
	signed domain = 1 << iota
	unsigned
	pointer
	boolean
)

var domainStrings = [...]string{
	"signed", "unsigned", "pointer", "boolean",
}

func (d domain) String() string {
	s := ""
	for i, ds := range domainStrings {
		if d&(1<<uint(i)) != 0 {
			if len(s) != 0 {
				s += "|"
			}
			s += ds
			d &^= 1 << uint(i)
		}
	}
	if d != 0 {
		if len(s) != 0 {
			s += "|"
		}
		s += fmt.Sprintf("0x%x", uint(d))
	}
	return s
}

type pair struct {
	v, w *Value // 一对值，按ID排序。
	// v可以是零，表示零值。
	// 对于布尔型，零值（v==nil）为假。
	d domain
}

// 事实是一对加上一对的关系。
type fact struct {
	p pair
	r relation
}

// 极限记录值的已知上限和下限。
type limit struct {
	min, max   int64  // 最小值<=值<=最大值，有符号
	umin, umax uint64 // umin<=值<=umax，无符号
}

func (l limit) String() string {
	return fmt.Sprintf("sm,SM,um,UM=%d,%d,%d,%d", l.min, l.max, l.umin, l.umax)
}

func (l limit) intersect(l2 limit) limit {
	if l.min < l2.min {
		l.min = l2.min
	}
	if l.umin < l2.umin {
		l.umin = l2.umin
	}
	if l.max > l2.max {
		l.max = l2.max
	}
	if l.umax > l2.umax {
		l.umax = l2.umax
	}
	return l
}

var noLimit = limit{math.MinInt64, math.MaxInt64, 0, math.MaxUint64}

// limitFact是特定值的已知极限。
type limitFact struct {
	vid   ID
	limit limit
}

// factsTable跟踪成对值之间的关系。
// None
// 事实表的逻辑是合理的，但不完整。在少数人之外
// 在特殊情况下，它不执行演绎或算术运算。在那里
// 是否为此制定了已知的决策程序，采取了特别的方法
// 通过事实表可以有效地处理实际代码，同时保持
// 有效率的
type factsTable struct {
	// 如果事实包含矛盾，则unsat为真。
	// None
	// 请注意，factsTable逻辑不完整，因此如果不满足
	// 如果是错误的，factsTable中的断言可能是令人满意的
	// *或者不满意。
	unsat      bool // 如果事实包含矛盾，则为true
	unsatDepth int  // unsat检查点的数量

	facts map[pair]relation // 当前已知关系集
	stack []fact            // 前几组关系

	// 顺序是记录信息的两个偏序集
	// 关于有符号和无符号中SSA值之间的关系
	// 领域
	orderS *poset
	orderU *poset

	// 单个值的已知上下限。
	limits     map[ID]limit
	limitStack []limitFact // 以前的条目

	// 对于每个切片s，从s到len（s）/cap（s）值（如果有）的映射
	// TODO:检查是否有重要的案例
	// 一个切片有多个透镜。如有必要，我们可以保留一份清单。
	lens map[ID]*Value
	caps map[ID]*Value

	// 零是一个零值常量
	zero *Value
}

// checkpointFact是用于检查点的无效值
// 恢复稳定。
var checkpointFact = fact{}
var checkpointBound = limitFact{}

func newFactsTable(f *Func) *factsTable {
	ft := &factsTable{}
	ft.orderS = f.newPoset()
	ft.orderU = f.newPoset()
	ft.orderS.SetUnsigned(false)
	ft.orderU.SetUnsigned(true)
	ft.facts = make(map[pair]relation)
	ft.stack = make([]fact, 4)
	ft.limits = make(map[ID]limit)
	ft.limitStack = make([]limitFact, 4)
	ft.zero = f.ConstInt64(f.Config.Types.Int64, 0)
	return ft
}

// 更新域d中v和w之间的关系集
// 把它限制在r。
func (ft *factsTable) update(parent *Block, v, w *Value, d domain, r relation) {
	if parent.Func.pass.debug > 2 {
		parent.Func.Warnl(parent.Pos, "parent=%s, update %s %s %s", parent, v, w, r)
	}
	// 如果我们已经找到了unsat，就不需要做任何其他事情。
	if ft.unsat {
		return
	}

	// 事实真相。把它记录在事实中是浪费的
	// 表，所以只需注意它是否令人满意
	if v == w {
		if r&eq == 0 {
			ft.unsat = true
		}
		return
	}

	if d == signed || d == unsigned {
		var ok bool
		order := ft.orderS
		if d == unsigned {
			order = ft.orderU
		}
		switch r {
		case lt:
			ok = order.SetOrder(v, w)
		case gt:
			ok = order.SetOrder(w, v)
		case lt | eq:
			ok = order.SetOrderOrEqual(v, w)
		case gt | eq:
			ok = order.SetOrderOrEqual(w, v)
		case eq:
			ok = order.SetEqual(v, w)
		case lt | gt:
			ok = order.SetNonEqual(v, w)
		default:
			panic("unknown relation")
		}
		if !ok {
			if parent.Func.pass.debug > 2 {
				parent.Func.Warnl(parent.Pos, "unsat %s %s %s", v, w, r)
			}
			ft.unsat = true
			return
		}
	} else {
		if lessByID(w, v) {
			v, w = w, v
			r = reverseBits[r]
		}

		p := pair{v, w, d}
		oldR, ok := ft.facts[p]
		if !ok {
			if v == w {
				oldR = eq
			} else {
				oldR = lt | eq | gt
			}
		}
		// 与事实表中已有的信息相比，无任何更改。
		if oldR == r {
			return
		}
		ft.stack = append(ft.stack, fact{p, oldR})
		ft.facts[p] = oldR & r
		// 如果此关系不可满足，请标记它并立即退出
		if oldR&r == 0 {
			if parent.Func.pass.debug > 2 {
				parent.Func.Warnl(parent.Pos, "unsat %s %s %s", v, w, r)
			}
			ft.unsat = true
			return
		}
	}

	// 与常量比较时提取边界
	if v.isGenericIntConst() {
		v, w = w, v
		r = reverseBits[r]
	}
	if v != nil && w.isGenericIntConst() {
		// 注：以下所有+1/-1可能会溢出/下溢。要么
		// 如果仍然生成正确的结果，则只会导致不精确。
		// 事实上，如果存在溢出/下溢，则相应的
		// 代码无法访问，因为已知范围超出范围
		// 值的类型。
		old, ok := ft.limits[v.ID]
		if !ok {
			old = noLimit
			if v.isGenericIntConst() {
				switch d {
				case signed:
					old.min, old.max = v.AuxInt, v.AuxInt
					if v.AuxInt >= 0 {
						old.umin, old.umax = uint64(v.AuxInt), uint64(v.AuxInt)
					}
				case unsigned:
					old.umin = v.AuxUnsigned()
					old.umax = old.umin
					if int64(old.umin) >= 0 {
						old.min, old.max = int64(old.umin), int64(old.umin)
					}
				}
			}
		}
		lim := noLimit
		switch d {
		case signed:
			c := w.AuxInt
			switch r {
			case lt:
				lim.max = c - 1
			case lt | eq:
				lim.max = c
			case gt | eq:
				lim.min = c
			case gt:
				lim.min = c + 1
			case lt | gt:
				lim = old
				if c == lim.min {
					lim.min++
				}
				if c == lim.max {
					lim.max--
				}
			case eq:
				lim.min = c
				lim.max = c
			}
			if lim.min >= 0 {
				// None
				lim.umin = uint64(lim.min)
			}
			if lim.max != noLimit.max && old.min >= 0 && lim.max >= 0 {
				// None
				// 这是一个最大更新，所以下限
				// 来自我们已经知道的（旧的）。
				lim.umax = uint64(lim.max)
			}
		case unsigned:
			uc := w.AuxUnsigned()
			switch r {
			case lt:
				lim.umax = uc - 1
			case lt | eq:
				lim.umax = uc
			case gt | eq:
				lim.umin = uc
			case gt:
				lim.umin = uc + 1
			case lt | gt:
				lim = old
				if uc == lim.umin {
					lim.umin++
				}
				if uc == lim.umax {
					lim.umax--
				}
			case eq:
				lim.umin = uc
				lim.umax = uc
			}
			// 我们可以利用
			// 有符号的含义来推导有符号的事实，
			// 但事实证明这无关紧要。
		}
		ft.limitStack = append(ft.limitStack, limitFact{v.ID, old})
		lim = old.intersect(lim)
		ft.limits[v.ID] = lim
		if v.Block.Func.pass.debug > 2 {
			v.Block.Func.Warnl(parent.Pos, "parent=%s, new limits %s %s %s %s", parent, v, w, r, lim.String())
		}
		if lim.min > lim.max || lim.umin > lim.umax {
			ft.unsat = true
			return
		}
	}

	// 下面的衍生事实仅与数字有关。
	if d != signed && d != unsigned {
		return
	}

	// 鉴于len和cap之间的关系，我们知道的其他事实。
	// None
	// TODO:因为现在证明派生了传递关系，所以
	// 应足以了解len（w）<=上限（w）
	// 开始证明我们在哪里寻找所有len/cap操作。
	if v.Op == OpSliceLen && r&lt == 0 && ft.caps[v.Args[0].ID] != nil {
		// len（s）>w意味着cap（s）>w
		// len（s）>=w意味着cap（s）>=w
		// len（s）==w意味着cap（s）>=w
		ft.update(parent, ft.caps[v.Args[0].ID], w, d, r|gt)
	}
	if w.Op == OpSliceLen && r&gt == 0 && ft.caps[w.Args[0].ID] != nil {
		// 相同，右侧的长度相同。
		ft.update(parent, v, ft.caps[w.Args[0].ID], d, r|lt)
	}
	if v.Op == OpSliceCap && r&gt == 0 && ft.lens[v.Args[0].ID] != nil {
		// 封盖<w表示长度<w
		// 盖<=w表示长度<=w
		// 封盖==w表示长度<=w
		ft.update(parent, ft.lens[v.Args[0].ID], w, d, r|lt)
	}
	if w.Op == OpSliceCap && r&lt == 0 && ft.lens[w.Args[0].ID] != nil {
		// 相同，RHS上的容量。
		ft.update(parent, v, ft.lens[w.Args[0].ID], d, r|gt)
	}

	// 过程围栏后的影响。
	// None
	// 首先，使条件>或>=。
	if r == lt || r == lt|eq {
		v, w = w, v
		r = reverseBits[r]
	}
	switch r {
	case gt:
		if x, delta := isConstDelta(v); x != nil && delta == 1 {
			// None
			// None
			// 这有助于消除错误
			// 生长追加的切片分支。
			ft.update(parent, x, w, d, gt|eq)
		} else if x, delta := isConstDelta(w); x != nil && delta == -1 {
			// None
			ft.update(parent, v, x, d, gt|eq)
		}
	case gt | eq:
		if x, delta := isConstDelta(v); x != nil && delta == -1 {
			// None
			// None
			// 对i>0有用；s[i-1]。
			lim, ok := ft.limits[x.ID]
			if ok && ((d == signed && lim.min > opMin[v.Op]) || (d == unsigned && lim.umin > 0)) {
				ft.update(parent, x, w, d, gt)
			}
		} else if x, delta := isConstDelta(w); x != nil && delta == 1 {
			// None
			lim, ok := ft.limits[x.ID]
			if ok && ((d == signed && lim.max < opMax[w.Op]) || (d == unsigned && lim.umax < opUMax[w.Op])) {
				ft.update(parent, v, x, d, gt)
			}
		}
	}

	// 过程：x+delta>w（具有delta常数）
	// 目前只有已签名的域（用于访问循环中的切片）。
	if r == gt || r == gt|eq {
		if x, delta := isConstDelta(v); x != nil && d == signed {
			if parent.Func.pass.debug > 1 {
				parent.Func.Warnl(parent.Pos, "x+d %s w; x:%v %v delta:%v w:%v d:%v", r, x, parent.String(), delta, w.AuxInt, d)
			}
			if !w.isGenericIntConst() {
				// 如果我们知道x+delta>w，但w不是常数，我们可以得出：
				// 如果delta<0且x>MinInt-delta，则x>w（因为x+delta不能下溢）
				// 这对于边界为“len（slice）-K”（delta=-K）的循环很有用
				if l, has := ft.limits[x.ID]; has && delta < 0 {
					if (x.Type.Size() == 8 && l.min >= math.MinInt64-delta) ||
						(x.Type.Size() == 4 && l.min >= math.MinInt32-delta) {
						ft.update(parent, x, w, signed, r)
					}
				}
			} else {
				// None
				// None
				// 我们计算（使用正确大小的整数）：
				// 最小值=w-增量
				// max=MaxInt-delta
				// None
				// 我们证明：
				// 如果最小值<最大值：最小值<x且x<=最大值
				// 如果最小值>最大值：最小值<x或x<=最大值
				// None
				// 即使在溢出的情况下，这也是正确的。
				// None
				// 如果初始事实为x+delta>=w，则派生条件为：
				// 如果最小值<最大值：最小值<=x和x<=max
				// 如果最小值>最大值：最小值<=x或x<=最大值
				// None
				// 请注意，max的条件仍然<=，因为它们处理溢出。
				var min, max int64
				var vmin, vmax *Value
				switch x.Type.Size() {
				case 8:
					min = w.AuxInt - delta
					max = int64(^uint64(0)>>1) - delta

					vmin = parent.NewValue0I(parent.Pos, OpConst64, parent.Func.Config.Types.Int64, min)
					vmax = parent.NewValue0I(parent.Pos, OpConst64, parent.Func.Config.Types.Int64, max)

				case 4:
					min = int64(int32(w.AuxInt) - int32(delta))
					max = int64(int32(^uint32(0)>>1) - int32(delta))

					vmin = parent.NewValue0I(parent.Pos, OpConst32, parent.Func.Config.Types.Int32, min)
					vmax = parent.NewValue0I(parent.Pos, OpConst32, parent.Func.Config.Types.Int32, max)

				default:
					panic("unimplemented")
				}

				if min < max {
					// 记录x>最小值和最大值>=x
					ft.update(parent, x, vmin, d, r)
					ft.update(parent, vmax, x, d, r|eq)
				} else {
					// 我们知道x>min或x<=max.factsTable无法记录或记录条件，
					// 那么让我们看看我们是否已经可以证明其中一个是假的，在这种情况下
					// 另一个肯定是真的
					if l, has := ft.limits[x.ID]; has {
						if l.max <= min {
							if r&eq == 0 || l.max < min {
								// x> min（x>=min）是不可能的，因此它必须是x<=max
								ft.update(parent, vmax, x, d, r|eq)
							}
						} else if l.min > max {
							// x<=max是不可能的，因此它必须是x>min
							ft.update(parent, x, vmin, d, r)
						}
					}
				}
			}
		}
	}

	// 查看保留值的扩展。
	// 如果域适用于预扩展类型，
	// 使用预扩展值重复更新。
	if isCleanExt(v) {
		switch {
		case d == signed && v.Args[0].Type.IsSigned():
			fallthrough
		case d == unsigned && !v.Args[0].Type.IsSigned():
			ft.update(parent, v.Args[0], w, d, r)
		}
	}
	if isCleanExt(w) {
		switch {
		case d == signed && w.Args[0].Type.IsSigned():
			fallthrough
		case d == unsigned && !w.Args[0].Type.IsSigned():
			ft.update(parent, v, w.Args[0], d, r)
		}
	}
}

var opMin = map[Op]int64{
	OpAdd64: math.MinInt64, OpSub64: math.MinInt64,
	OpAdd32: math.MinInt32, OpSub32: math.MinInt32,
}

var opMax = map[Op]int64{
	OpAdd64: math.MaxInt64, OpSub64: math.MaxInt64,
	OpAdd32: math.MaxInt32, OpSub32: math.MaxInt32,
}

var opUMax = map[Op]uint64{
	OpAdd64: math.MaxUint64, OpSub64: math.MaxUint64,
	OpAdd32: math.MaxUint32, OpSub32: math.MaxUint32,
}

// isNonNegative报告v是否已知为非负。
func (ft *factsTable) isNonNegative(v *Value) bool {
	if isNonNegative(v) {
		return true
	}

	var max int64
	switch v.Type.Size() {
	case 1:
		max = math.MaxInt8
	case 2:
		max = math.MaxInt16
	case 4:
		max = math.MaxInt32
	case 8:
		max = math.MaxInt64
	default:
		panic("unexpected integer size")
	}

	// 检查记录的限值是否能证明该值为正值

	if l, has := ft.limits[v.ID]; has && (l.min >= 0 || l.umax <= uint64(max)) {
		return true
	}

	// 检查v=x+delta，我们可以用x的极限来证明它是正的
	if x, delta := isConstDelta(v); x != nil {
		if l, has := ft.limits[x.ID]; has {
			if delta > 0 && l.min >= -delta && l.max <= max-delta {
				return true
			}
			if delta < 0 && l.min >= -delta {
				return true
			}
		}
	}

	// 检查v是否是非负值的保值扩展。
	if isCleanExt(v) && ft.isNonNegative(v.Args[0]) {
		return true
	}

	// 检查签名偏序集是否可以证明值>=0
	return ft.orderS.OrderedOrEqual(ft.zero, v)
}

// 检查点保存已知关系的当前状态。
// 在分支上下降时调用。
func (ft *factsTable) checkpoint() {
	if ft.unsat {
		ft.unsatDepth++
	}
	ft.stack = append(ft.stack, checkpointFact)
	ft.limitStack = append(ft.limitStack, checkpointBound)
	ft.orderS.Checkpoint()
	ft.orderU.Checkpoint()
}

// restore恢复与状态的已知关系
// 在上一个检查站之前。
// 备份分支时调用。
func (ft *factsTable) restore() {
	if ft.unsatDepth > 0 {
		ft.unsatDepth--
	} else {
		ft.unsat = false
	}
	for {
		old := ft.stack[len(ft.stack)-1]
		ft.stack = ft.stack[:len(ft.stack)-1]
		if old == checkpointFact {
			break
		}
		if old.r == lt|eq|gt {
			delete(ft.facts, old.p)
		} else {
			ft.facts[old.p] = old.r
		}
	}
	for {
		old := ft.limitStack[len(ft.limitStack)-1]
		ft.limitStack = ft.limitStack[:len(ft.limitStack)-1]
		if old.vid == 0 { // 检查点边界
			break
		}
		if old.limit == noLimit {
			delete(ft.limits, old.vid)
		} else {
			ft.limits[old.vid] = old.limit
		}
	}
	ft.orderS.Undo()
	ft.orderU.Undo()
}

func lessByID(v, w *Value) bool {
	if v == nil && w == nil {
		// 不应该发生，只是以防万一。
		return false
	}
	if v == nil {
		return true
	}
	return w != nil && v.ID < w.ID
}

var (
	reverseBits = [...]relation{0, 4, 2, 6, 1, 5, 3, 7}

	// 映射我们在执行正分支时所了解的内容。
	// 例如：
	// OpLess8:{已签名，lt}，
	// v1=（OpLess8 v2 v3）。
	// 如果采用v1分支，则我们了解到rangeMask
	// 最多可以是中尉。
	domainRelationTable = map[Op]struct {
		d domain
		r relation
	}{
		OpEq8:   {signed | unsigned, eq},
		OpEq16:  {signed | unsigned, eq},
		OpEq32:  {signed | unsigned, eq},
		OpEq64:  {signed | unsigned, eq},
		OpEqPtr: {pointer, eq},

		OpNeq8:   {signed | unsigned, lt | gt},
		OpNeq16:  {signed | unsigned, lt | gt},
		OpNeq32:  {signed | unsigned, lt | gt},
		OpNeq64:  {signed | unsigned, lt | gt},
		OpNeqPtr: {pointer, lt | gt},

		OpLess8:   {signed, lt},
		OpLess8U:  {unsigned, lt},
		OpLess16:  {signed, lt},
		OpLess16U: {unsigned, lt},
		OpLess32:  {signed, lt},
		OpLess32U: {unsigned, lt},
		OpLess64:  {signed, lt},
		OpLess64U: {unsigned, lt},

		OpLeq8:   {signed, lt | eq},
		OpLeq8U:  {unsigned, lt | eq},
		OpLeq16:  {signed, lt | eq},
		OpLeq16U: {unsigned, lt | eq},
		OpLeq32:  {signed, lt | eq},
		OpLeq32U: {unsigned, lt | eq},
		OpLeq64:  {signed, lt | eq},
		OpLeq64U: {unsigned, lt | eq},

		// 对于这些老年退休金计划，消极的分支是不同的：我们只能
		// 如果我们可以证明arg0是非负的，则证明signed/GE（signed/GT）。
		// 请参见addBranchRestrictions中的特殊情况。
		OpIsInBounds:      {signed | unsigned, lt},      // 0<=arg0<arg1
		OpIsSliceInBounds: {signed | unsigned, lt | eq}, // 0<=arg0<=arg1
	}
)

// 清除将偏序集返回到自由列表
func (ft *factsTable) cleanup(f *Func) {
	for _, po := range []*poset{ft.orderS, ft.orderU} {
		// 确保它是空的，因为它应该是。非空偏序集
		// 如果重复使用，可能会导致错误和错误编译。
		if checkEnabled {
			if err := po.CheckEmpty(); err != nil {
				f.Fatalf("poset not empty after function %s: %v", f.Name, err)
			}
		}
		f.retPoset(po)
	}
}

// prove删除可推断的冗余BlockIf分支
// 从以前的主要比较中。
// None
// 到目前为止，最常见的冗余对是通过边界检查生成的。
// 例如，对于代码：
// None
// a[i]=4
// foo（a[i]）
// None
// 编译器将生成以下代码：
// None
// 如果i>=len（a）{
// 恐慌（“不受限制”）
// }
// a[i]=4
// 如果i>=len（a）{
// 恐慌（“不受限制”）
// }
// foo（a[i]）
// None
// 第二个比较i>=len（a）显然是多余的，因为
// 否则执行第一个比较的分支，我们已经知道i<len（a）。
// 可以删除第二次紧急情况的代码。
// None
// 通过发现矛盾和修剪树枝来证明作品
// 鉴于通向这些条件的分支机构，这些条件是不可满足的。
// 它跟踪分支条件的“事实表”。对于每个分支
// 块，它断言唯一支配该块的分支条件
// 块，然后分别断言块的分支条件和
// 它的否定。如果其中任何一个导致矛盾，它都可以消除矛盾
// 继承人
func prove(f *Func) {
	ft := newFactsTable(f)
	ft.checkpoint()

	var lensVars map[*Block][]*Value

	// 查找长度和容量。
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			if v.Uses == 0 {
				// 我们不在乎死价值观。
				// （可能有一些是CSD，但尚未删除。）
				continue
			}
			switch v.Op {
			case OpStringLen:
				ft.update(b, v, ft.zero, signed, gt|eq)
			case OpSliceLen:
				if ft.lens == nil {
					ft.lens = map[ID]*Value{}
				}
				// 将同一切片的所有len值设置为偏序集中的相等值。
				// 偏序集处理传递关系，因此值与
				// 此切片的任何OpSliceLen都将与其他切片正确关联。
				if l, ok := ft.lens[v.Args[0].ID]; ok {
					ft.update(b, v, l, signed, eq)
				} else {
					ft.lens[v.Args[0].ID] = v
				}
				ft.update(b, v, ft.zero, signed, gt|eq)
				if v.Args[0].Op == OpSliceMake {
					if lensVars == nil {
						lensVars = make(map[*Block][]*Value)
					}
					lensVars[b] = append(lensVars[b], v)
				}
			case OpSliceCap:
				if ft.caps == nil {
					ft.caps = map[ID]*Value{}
				}
				// 与上述OpSliceLen的情况相同，但适用于切片帽。
				if c, ok := ft.caps[v.Args[0].ID]; ok {
					ft.update(b, v, c, signed, eq)
				} else {
					ft.caps[v.Args[0].ID] = v
				}
				ft.update(b, v, ft.zero, signed, gt|eq)
				if v.Args[0].Op == OpSliceMake {
					if lensVars == nil {
						lensVars = make(map[*Block][]*Value)
					}
					lensVars[b] = append(lensVars[b], v)
				}
			}
		}
	}

	// 寻找归纳变量。目前，findIndVars
	// 每个块仅限于一个感应变量。
	var indVars map[*Block]indVar
	for _, v := range findIndVar(f) {
		if indVars == nil {
			indVars = make(map[*Block]indVar)
		}
		indVars[v.entry] = v
	}

	// 当前节点状态
	type walkState int
	const (
		descend walkState = iota
		simplify
	)
	// 工作维护DFS堆栈。
	type bp struct {
		block *Block    // 当前处理块
		state walkState // 怎么办
	}
	work := make([]bp, 0, 256)
	work = append(work, bp{
		block: f.Entry,
		state: descend,
	})

	idom := f.Idom()
	sdom := f.Sdom()

	// 控制树上的DFS。
	// None
	// 对于效率，我们只考虑支配树。
	// 而不是整个流程图。在途中，我们考虑
	// 传入的分支和累积的条件
	// 控制当前区块。如果发现矛盾,，
	// 我们可以消灭整个街区和它的所有孩子。
	// 在备份的过程中，我们考虑输出分支
	// 还没有考虑过。这样我们考虑每个
	// 分支条件只有一次。
	for len(work) > 0 {
		node := work[len(work)-1]
		work = work[:len(work)-1]
		parent := idom[node.block.ID]
		branch := getBranch(sdom, parent, node.block)

		switch node.state {
		case descend:
			ft.checkpoint()

			// 进入块，根据我们收集的事实添加块
			// 开始时：诱导变量和切片的镜头/封盖。
			if iv, ok := indVars[node.block]; ok {
				addIndVarRestrictions(ft, parent, iv)
			}
			if lens, ok := lensVars[node.block]; ok {
				for _, v := range lens {
					switch v.Op {
					case OpSliceLen:
						ft.update(node.block, v, v.Args[0].Args[1], signed, eq)
					case OpSliceCap:
						ft.update(node.block, v, v.Args[0].Args[2], signed, eq)
					}
				}
			}

			if branch != unknown {
				addBranchRestrictions(ft, parent, branch)
				if ft.unsat {
					// 无法访问node.block。
					// 删除它，不要访问
					// 它的孩子。
					removeBranch(parent, branch)
					ft.restore()
					break
				}
				// 否则，我们现在可以承诺
				// 拿着这个树枝。我们会恢复的
				// 当我们放松的时候。
			}

			// 在此块中添加潜在危险装置的归纳事实。
			addLocalInductiveFacts(ft, node.block)

			work = append(work, bp{
				block: node.block,
				state: simplify,
			})
			for s := sdom.Child(node.block); s != nil; s = sdom.Sibling(s) {
				work = append(work, bp{
					block: s,
					state: descend,
				})
			}

		case simplify:
			simplifyBlock(sdom, ft, node.block)
			ft.restore()
		}
	}

	ft.restore()

	ft.cleanup(f)
}

// getBranch返回p添加的范围限制
// 当到达b。p是b的直接支配者。
func getBranch(sdom SparseTree, p *Block, b *Block) branch {
	if p == nil || p.Kind != BlockIf {
		return unknown
	}
	// 如果p和p.Succs[0]是支配者，则表示每条路径
	// 从条目到b经过p和p.Succs[0]。我们关心那件事
	// 没有从入口到b的路径通过p.Succs[1]。如果p.Succs[0]
	// 有一个前身（除退化情况外），
	// 没有从入口到b通过p.Succs[1]的路径。
	// TODO:p->yes->b->yes如何，即yes中的循环。
	if sdom.IsAncestorEq(p.Succs[0].b, b) && len(p.Succs[0].b.Preds) == 1 {
		return positive
	}
	if sdom.IsAncestorEq(p.Succs[1].b, b) && len(p.Succs[1].b.Preds) == 1 {
		return negative
	}
	return unknown
}

// addIndVarRestrictions使用事实更新factsTables ft
// 从驱动回路的感应变量indVar中学习
// 从b区开始。
func addIndVarRestrictions(ft *factsTable, b *Block, iv indVar) {
	d := signed
	if ft.isNonNegative(iv.min) && ft.isNonNegative(iv.max) {
		d |= unsigned
	}

	if iv.flags&indVarMinExc == 0 {
		addRestrictions(b, ft, d, iv.min, iv.ind, lt|eq)
	} else {
		addRestrictions(b, ft, d, iv.min, iv.ind, lt)
	}

	if iv.flags&indVarMaxInc == 0 {
		addRestrictions(b, ft, d, iv.ind, iv.max, lt)
	} else {
		addRestrictions(b, ft, d, iv.ind, iv.max, lt|eq)
	}
}

// addBranchRestrictions使用在
// 从b区向br方向分支。
func addBranchRestrictions(ft *factsTable, b *Block, br branch) {
	c := b.Controls[0]
	switch br {
	case negative:
		addRestrictions(b, ft, boolean, nil, c, eq)
	case positive:
		addRestrictions(b, ft, boolean, nil, c, lt|gt)
	default:
		panic("unknown branch")
	}
	if tr, has := domainRelationTable[c.Op]; has {
		// 当我们从父母那里分道扬镳时，我们学会了一套新的方法
		// 限制。相应地更新factsTable。
		d := tr.d
		if d == signed && ft.isNonNegative(c.Args[0]) && ft.isNonNegative(c.Args[1]) {
			d |= unsigned
		}
		switch c.Op {
		case OpIsInBounds, OpIsSliceInBounds:
			// 0<=a0<a1（或0<=a0<=a1）
			// None
			// 在积极方面，我们了解到：
			// 签名：0<=a0<a1（或0<=a0<=a1）
			// 无符号：a0<a1（或a0<=a1）
			// None
			// 在负分支上，我们学习（0>a0）||
			// a0>=a1）。在未签名域中，这是
			// 只需a0>=a1（与
			// 正分支，所以没什么奇怪的）。
			// 但在签名域中，我们无法表示||
			// 条件，因此检查a0是否为非负，
			// 能够学到一些东西。
			switch br {
			case negative:
				d = unsigned
				if ft.isNonNegative(c.Args[0]) {
					d |= signed
				}
				addRestrictions(b, ft, d, c.Args[0], c.Args[1], tr.r^(lt|gt|eq))
			case positive:
				addRestrictions(b, ft, signed, ft.zero, c.Args[0], lt|eq)
				addRestrictions(b, ft, d, c.Args[0], c.Args[1], tr.r)
			}
		default:
			switch br {
			case negative:
				addRestrictions(b, ft, d, c.Args[0], c.Args[1], tr.r^(lt|gt|eq))
			case positive:
				addRestrictions(b, ft, d, c.Args[0], c.Args[1], tr.r)
			}
		}

	}
}

// addRestrictions从即时列表更新限制
// 使用r的控制块（p）。
func addRestrictions(parent *Block, ft *factsTable, t domain, v, w *Value, r relation) {
	if t == 0 {
		// 小事：无事可做。
		// 不应该发生，只是以防万一。
		return
	}
	for i := domain(1); i <= t; i <<= 1 {
		if t&i == 0 {
			continue
		}
		ft.update(parent, v, w, i, r)
	}
}

// addLocalInductiveFacts在访问b时添加归纳事实，其中
// b是循环中的连接点。与findIndVar相比，这
// 取决于为b确定的事实，这就是为什么在
// 访问b。addLocalInductiveFacts专门针对该模式
// 由OfRuntil创建，findIndVar未检测到它。
// None
// TODO:把这个和findIndVar结合起来会很好。
func addLocalInductiveFacts(ft *factsTable, b *Block) {
	// 这将查找特定的归纳模式：
	// None
	// 1.i1=b中的OpPhi（最小值，i2）
	// 2.i2=i1+1
	// 3.i2<b.Preds出口处的最大值[1]
	// 4.最小值<最大值
	// None
	// 如果所有这些条件均为真，则i1<max和i1>=min。

	// 确保这是一个循环头节点。
	if len(b.Preds) != 2 {
		return
	}

	for _, i1 := range b.Values {
		if i1.Op != OpPhi {
			continue
		}

		// 检查有无条件1和2。这很容易做到
		// 并将扔掉大部分网络钓鱼。
		min, i2 := i1.Args[0], i1.Args[1]
		if i1q, delta := isConstDelta(i2); i1q != i1 || delta != 1 {
			continue
		}

		// 试着证明条件3。我们不能只是质疑
		// 事实表，因为我们不知道
		// b.Preds[1]的事实是（一般来说，b.Preds[1]是
		// 一个环回边缘，所以我们甚至没有去过那里
		// 然而）。作为保守近似，我们寻找
		// 此条件在前一个链中，直到我们
		// 击中连接点。
		uniquePred := func(b *Block) *Block {
			if len(b.Preds) == 1 {
				return b.Preds[0].b
			}
			return nil
		}
		pred, child := b.Preds[1].b, b
		for ; pred != nil; pred, child = uniquePred(pred), pred {
			if pred.Kind != BlockIf {
				continue
			}
			control := pred.Controls[0]

			br := unknown
			if pred.Succs[0].b == child {
				br = positive
			}
			if pred.Succs[1].b == child {
				if br != unknown {
					continue
				}
				br = negative
			}
			if br == unknown {
				continue
			}

			tr, has := domainRelationTable[control.Op]
			if !has {
				continue
			}
			r := tr.r
			if br == negative {
				// 负分支到达b。
				// 补充关系。
				r = (lt | eq | gt) ^ r
			}

			// 检查i2是否小于最大值或最大值是否大于i2。
			var max *Value
			if r == lt && control.Args[0] == i2 {
				max = control.Args[1]
			} else if r == gt && control.Args[1] == i2 {
				max = control.Args[0]
			} else {
				continue
			}

			// 检查条件4，现在我们有一个
			// 候选最大值。对于此，我们可以查询
			// 事实表。我们通过显示“证明”最小值<最大值
			// 最小值>=最大值未设定。（这可能很简单
			// 比较两个常数；好的。）
			ft.checkpoint()
			ft.update(b, min, max, tr.d, gt|eq)
			proved := ft.unsat
			ft.restore()

			if proved {
				// 我们知道min<=i1<max。
				if b.Func.pass.debug > 0 {
					printIndVar(b, i1, min, max, 1, 0)
				}
				ft.update(b, min, i1, tr.d, lt|eq)
				ft.update(b, i1, max, tr.d, lt)
			}
		}
	}
}

var ctzNonZeroOp = map[Op]Op{OpCtz8: OpCtz8NonZero, OpCtz16: OpCtz16NonZero, OpCtz32: OpCtz32NonZero, OpCtz64: OpCtz64NonZero}
var mostNegativeDividend = map[Op]int64{
	OpDiv16: -1 << 15,
	OpMod16: -1 << 15,
	OpDiv32: -1 << 31,
	OpMod32: -1 << 31,
	OpDiv64: -1 << 63,
	OpMod64: -1 << 63}

// simplifyBlock简化b中的一些常量值并计算
// 分支到非唯一支配的b。
func simplifyBlock(sdom SparseTree, ft *factsTable, b *Block) {
	for _, v := range b.Values {
		switch v.Op {
		case OpSlicemask:
			// 尽可能用常量替换b中的OpSlicemask操作。
			x, delta := isConstDelta(v.Args[0])
			if x == nil {
				continue
			}
			// 切片掩模（x+y）
			// 如果x大于-y（y为负），则切片掩码为-1。
			lim, ok := ft.limits[x.ID]
			if !ok {
				continue
			}
			if lim.umin > uint64(-delta) {
				if v.Args[0].Op == OpAdd64 {
					v.reset(OpConst64)
				} else {
					v.reset(OpConst32)
				}
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(v.Pos, "Proved slicemask not needed")
				}
				v.AuxInt = -1
			}
		case OpCtz8, OpCtz16, OpCtz32, OpCtz64:
			// 在某些体系结构上，尤其是在amd64上，我们可以生成更好的
			// 如果我们知道参数为非零，则使用CtzNN代码。
			// 在这里捕获这些信息，以便在特定于arch的优化中使用。
			x := v.Args[0]
			lim, ok := ft.limits[x.ID]
			if !ok {
				continue
			}
			if lim.umin > 0 || lim.min > 0 || lim.max < 0 {
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(v.Pos, "Proved %v non-zero", v.Op)
				}
				v.Op = ctzNonZeroOp[v.Op]
			}
		case OpRsh8x8, OpRsh8x16, OpRsh8x32, OpRsh8x64,
			OpRsh16x8, OpRsh16x16, OpRsh16x32, OpRsh16x64,
			OpRsh32x8, OpRsh32x16, OpRsh32x32, OpRsh32x64,
			OpRsh64x8, OpRsh64x16, OpRsh64x32, OpRsh64x64:
			// 检查对于a>>b，我们是否知道a是非负的
			// b是a的所有位，除了MSB。如果是这样，a将被移到零。
			bits := 8 * v.Type.Size()
			if v.Args[1].isGenericIntConst() && v.Args[1].AuxInt >= bits-1 && ft.isNonNegative(v.Args[0]) {
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(v.Pos, "Proved %v shifts to zero", v.Op)
				}
				switch bits {
				case 64:
					v.reset(OpConst64)
				case 32:
					v.reset(OpConst32)
				case 16:
					v.reset(OpConst16)
				case 8:
					v.reset(OpConst8)
				default:
					panic("unexpected integer size")
				}
				v.AuxInt = 0
				continue // 一定不要犯错误——这不再是一种老生常谈。
			}
			// 如果Rsh没有被0替换，仍然检查它是否有界。
			fallthrough
		case OpLsh8x8, OpLsh8x16, OpLsh8x32, OpLsh8x64,
			OpLsh16x8, OpLsh16x16, OpLsh16x32, OpLsh16x64,
			OpLsh32x8, OpLsh32x16, OpLsh32x32, OpLsh32x64,
			OpLsh64x8, OpLsh64x16, OpLsh64x32, OpLsh64x64,
			OpRsh8Ux8, OpRsh8Ux16, OpRsh8Ux32, OpRsh8Ux64,
			OpRsh16Ux8, OpRsh16Ux16, OpRsh16Ux32, OpRsh16Ux64,
			OpRsh32Ux8, OpRsh32Ux16, OpRsh32Ux32, OpRsh32Ux64,
			OpRsh64Ux8, OpRsh64Ux16, OpRsh64Ux32, OpRsh64Ux64:
			// 检查对于a<b，我们是否知道b
			// 严格小于a中的位数。
			by := v.Args[1]
			lim, ok := ft.limits[by.ID]
			if !ok {
				continue
			}
			bits := 8 * v.Args[0].Type.Size()
			if lim.umax < uint64(bits) || (lim.max < bits && ft.isNonNegative(by)) {
				v.AuxInt = 1 // 参见shiftIsBounded
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(v.Pos, "Proved %v bounded", v.Op)
				}
			}
		case OpDiv16, OpDiv32, OpDiv64, OpMod16, OpMod32, OpMod64:
			// 如果我们知道，amd64和386上的修复代码可以避免
			// 除数不是-1或股息>MinIntNN。
			// 不要在其他架构上修改生长素，
			// 因为这会干扰CSE。
			// TODO:添加其他体系结构？
			if b.Func.Config.arch != "386" && b.Func.Config.arch != "amd64" {
				break
			}
			divr := v.Args[1]
			divrLim, divrLimok := ft.limits[divr.ID]
			divd := v.Args[0]
			divdLim, divdLimok := ft.limits[divd.ID]
			if (divrLimok && (divrLim.max < -1 || divrLim.min > -1)) ||
				(divdLimok && divdLim.min > mostNegativeDividend[v.Op]) {
				// 请参阅rewrite.go中的分区需求修复。
				// v、 AuxInt=1意味着我们已经证明了除数不是-1
				// 股息不是最负的整数，
				// 因此，我们不需要添加修复代码。
				v.AuxInt = 1
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(v.Pos, "Proved %v does not need fix-up", v.Op)
				}
			}
		}
	}

	if b.Kind != BlockIf {
		return
	}

	// 考虑这个块的输出边。
	parent := b
	for i, branch := range [...]branch{positive, negative} {
		child := parent.Succs[i].b
		if getBranch(sdom, parent, child) != unknown {
			// 对于唯一支配块的边，我们
			// 我们去看孩子的时候已经这么做了。
			continue
		}
		// 对于其他块的边，这可以修剪分支
		// 即使我们不能摆脱孩子本身。
		ft.checkpoint()
		addBranchRestrictions(ft, parent, branch)
		unsat := ft.unsat
		ft.restore()
		if unsat {
			// 这根树枝是不可能的，所以把它移走
			// 从街区出来。
			removeBranch(parent, branch)
			// 没有必要考虑另一个分支。
			// （两者都有可能
			// 无法满足，因为事实表是
			// 不完整。我们可以把它变成一个
			// 封锁出口，但这似乎不值得。）
			break
		}
	}
}

func removeBranch(b *Block, branch branch) {
	c := b.Controls[0]
	if b.Func.pass.debug > 0 {
		verb := "Proved"
		if branch == positive {
			verb = "Disproved"
		}
		if b.Func.pass.debug > 1 {
			b.Func.Warnl(b.Pos, "%s %s (%s)", verb, c.Op, c)
		} else {
			b.Func.Warnl(b.Pos, "%s %s", verb, c.Op)
		}
	}
	if c != nil && c.Pos.IsStmt() == src.PosIsStmt && c.Pos.SameFileAndLine(b.Pos) {
		// 尝试保留语句标记。
		b.Pos = b.Pos.WithIsStmt()
	}
	b.Kind = BlockFirst
	b.ResetControls()
	if branch == positive {
		b.swapSuccessors()
	}
}

// isNonNegative报告v是否已知大于或等于零。
func isNonNegative(v *Value) bool {
	if !v.Type.IsInteger() {
		v.Fatalf("isNonNegative bad type: %v", v.Type)
	}
	// TODO:如果返回true！v、 类型.IsSigned（）
	// SSA的类型安全性还不够，现在无法做到这一点（第37753期）。
	// 下面的检查仅取决于位的模式。

	switch v.Op {
	case OpConst64:
		return v.AuxInt >= 0

	case OpConst32:
		return int32(v.AuxInt) >= 0

	case OpConst16:
		return int16(v.AuxInt) >= 0

	case OpConst8:
		return int8(v.AuxInt) >= 0

	case OpStringLen, OpSliceLen, OpSliceCap,
		OpZeroExt8to64, OpZeroExt16to64, OpZeroExt32to64,
		OpZeroExt8to32, OpZeroExt16to32, OpZeroExt8to16,
		OpCtz64, OpCtz32, OpCtz16, OpCtz8:
		return true

	case OpRsh64Ux64, OpRsh32Ux64:
		by := v.Args[1]
		return by.Op == OpConst64 && by.AuxInt > 0

	case OpRsh64x64, OpRsh32x64, OpRsh8x64, OpRsh16x64, OpRsh32x32, OpRsh64x32,
		OpSignExt32to64, OpSignExt16to64, OpSignExt8to64, OpSignExt16to32, OpSignExt8to32:
		return isNonNegative(v.Args[0])

	case OpAnd64, OpAnd32, OpAnd16, OpAnd8:
		return isNonNegative(v.Args[0]) || isNonNegative(v.Args[1])

	case OpMod64, OpMod32, OpMod16, OpMod8,
		OpDiv64, OpDiv32, OpDiv16, OpDiv8,
		OpOr64, OpOr32, OpOr16, OpOr8,
		OpXor64, OpXor32, OpXor16, OpXor8:
		return isNonNegative(v.Args[0]) && isNonNegative(v.Args[1])

		// 我们可以在这里处理OpPhi，但这样做的改进
		// 所以它们都很小，既不简单也不便宜。
	}
	return false
}

// 如果v等于w+delta（有符号），isConstDelta将返回非nil。
func isConstDelta(v *Value) (w *Value, delta int64) {
	cop := OpConst64
	switch v.Op {
	case OpAdd32, OpSub32:
		cop = OpConst32
	}
	switch v.Op {
	case OpAdd64, OpAdd32:
		if v.Args[0].Op == cop {
			return v.Args[1], v.Args[0].AuxInt
		}
		if v.Args[1].Op == cop {
			return v.Args[0], v.Args[1].AuxInt
		}
	case OpSub64, OpSub32:
		if v.Args[1].Op == cop {
			aux := v.Args[1].AuxInt
			if aux != -aux { // 溢流太糟糕了
				return v.Args[0], -aux
			}
		}
	}
	return nil, 0
}

// isCleanExt报告v是否是保留值的结果
// 符号或零扩展
func isCleanExt(v *Value) bool {
	switch v.Op {
	case OpSignExt8to16, OpSignExt8to32, OpSignExt8to64,
		OpSignExt16to32, OpSignExt16to64, OpSignExt32to64:
		// signed->signed是唯一保留值的符号扩展
		return v.Args[0].Type.IsSigned() && v.Type.IsSigned()

	case OpZeroExt8to16, OpZeroExt8to32, OpZeroExt8to64,
		OpZeroExt16to32, OpZeroExt16to64, OpZeroExt32to64:
		// unsigned->signed/unsigned是保留值的零扩展名
		return !v.Args[0].Type.IsSigned()
	}
	return false
}
